/**
 * @returns {Array.<T>}
 * @template T
 */
Array.prototype.clone = function () {
    var temp = [];
    for (var i = 0; i < this.length; ++i) {
        temp.push(this[i]);
    }
    return temp;
};

/**
 * @returns {T}
 * @template T
 */
Array.prototype.top = function () {
    return this.length == 0 ? undefined : this[this.length - 1];
};

/**
 * @param {Array.<Symbol>} arr
 * @template T
 */
Array.prototype.equalsForSymbol = function (arr) {
    if (this.length !== arr.length) return false;
    for (var i = 0; i < this.length; ++i) {
        if (this[i].sym_vt !== arr[i].sym_vt) {
            return false;
        }
    }
    return true;
};

/**
 * @param {T} ele
 * @param {number} count
 * @template T
 */
Array.prototype.replaceTop = function (ele, count) {
    if (count > this.length) return undefined;
    var tmp = [];
    for (var i = 0; i < count; ++i) {
        tmp.push(this.pop());
    }
    this.push(ele);
    return tmp;
};

Array.prototype.clear = function () {
    this.length = 0;
};


////////////// Set Class
/**
 * 自定义集合类
 * @constructor
 * @template T
 */
function Set() {
    /**
     *
     * @type {Array.<T>}
     */
    this.con = [];
    this.size = 0;
}

/**
 * 由元素获取其索引
 * @param {T} ele
 * @returns {number}
 * @private
 */
Set.prototype.__index__ = function (ele) {
    var i;
    for (i = 0; i < this.con.length; ++i) {
        if (ele === this.con[i]) {
            return i;
        }
    }
    return -1;
};

/**
 * 向集合中加入元素
 * @param {T} ele
 * @returns {boolean} 是否加入成功
 * @template T
 */
Set.prototype.add = function (ele) {
    if (this.__index__(ele) !== -1) return false;
    this.con.push(ele);
    this.size = this.con.length;
    return true;
};

/**
 * 向集合中加入元素
 * @param {Set.<T>} ele
 * @returns {boolean} 是否加入成功
 * @template T
 */
Set.prototype.addSet = function (ele) {
    var b = false;
    for (var i = 0; i < ele.size; ++i) {
        b |= this.add(ele.get(i));
    }
    return b;
};

/**
 * 移除指定元素
 * @param {T} ele
 * @template T
 */
Set.prototype.remove = function (ele) {
    var tmp, i;
    if (this.size > 0 && (i = this.__index__(ele)) !== -1) {
        tmp = this.con.splice(i, 1);
        this.size = this.con.length;
    }
    return tmp;
};

Set.prototype.replace = function (old, rep) {
    this.remove(old);
    if (rep instanceof Set) {
        for (var i = 0; i < rep.size; ++i) {
            this.add(rep.get(i));
        }
    } else {
        this.add(rep);
    }
};

/**
 * 获取指定索引的数据
 * @param {number} index
 * @returns {T}
 */
Set.prototype.get = function (index) {
    if (index < 0 || index >= this.size)
        return undefined;
    return this.con[index];
};

/**
 * 本实例是否包含 o , 即 o 中的元素在 this 中全部出现
 * @param {Set.<T>} o
 */
Set.prototype.contains = function (o) {
    if (this.size === 0) return false;
    for (var i = 0; i < o.size; ++i) {
        if (this.__index__(o.get(i)) === -1)
            return false;
    }
    return true;
};

Set.prototype.toString = function () {
    return this.size === 0 ? "∅" : "{" + this.con.join(", ") + "}";
};

Set.prototype.clear = function () {
    this.size = 0;
    this.con.clear();
};


//////////////// Map Class
/**
 *
 * @constructor
 * @template T1, T2
 */
function Map() {
    /**
     * @type {Array.<T1>}
     */
    this.key = [];
    /**
     * @type {Array.<T2>}
     */
    this.val = [];
    /**
     * @type {number}
     */
    this.size = 0;
}

/**
 * 由键值获取其索引
 * @param {T1} key
 * @returns {number}
 * @private
 */
Map.prototype.__index__ = function (key) {
    var i;
    for (i = 0; i < this.key.length; ++i) {
        if (this.key[i] === key) {
            return i;
        }
    }
    return -1;
};

/**
 * 放入键值对
 * @param {T1} key
 * @param {T2} val
 * @returns {boolean} 是否存入成功
 */
Map.prototype.put = function (key, val) {
    if (this.__index__(key) !== -1) return false;
    this.key.push(key);
    this.val.push(val);
    this.size = this.key.length;
    return true;
};

/**
 * 由 key 值获得其 value
 * @param {T1|number} key
 * @returns {T2}
 */
Map.prototype.get = function (key) {
    if (this.size > 0) {
        var i;
        if (!isNaN(key)) {
            i = key;
        } else {
            i = this.__index__(key);
        }
        if (i !== -1) {
            return this.val[i];
        }
    }
};

/**
 * 获取索引位置的 key 值
 * @param index
 * @returns {T1}
 */
Map.prototype.getKey = function (index) {
    return this.key[index];
};

/**
 * 设置 key 的 值为 val
 * @param {T1} key
 * @param {T2} val
 * @returns {boolean} 是否设值成功
 */
Map.prototype.set = function (key, val) {
    if (this.size > 0) {
        var i = this.__index__(key);
        if (i !== -1) {
            this.val[i] = val;
            return true;
        }
    }
    return false;
};

/**
 * 移除指定值
 * @param {T1} key
 * @returns {*[]}
 */
Map.prototype.remove = function (key) {
    if (this.size > 0) {
        var i = this.__index__(key), tmpKey, tmpVal;
        if (i !== -1) {
            tmpKey = this.key.splice(i, 1);
            tmpVal = this.key.splice(i, 1);
            this.size = this.key.length;
            return [tmpKey, tmpVal];
        }
    }
};

Map.prototype.has = function (key) {
    if (this.size > 0) {
        return this.__index__(key) !== -1;
    }
    return false;
};

Map.prototype.toString = function () {
    var str = ['{\n'], i;
    for (i = 0; i < this.size; ++i) {
        str.push('\t{', this.key[i].toString(), ', ' + this.val[i].toString() + '}\n');
    }
    str.push('}');
    return str.join("");
};

Map.prototype.clear = function () {
    this.size = 0;
    this.key.clear();
    this.val.clear();
};


///////////////// Compare Class
var Compare = {
    NUL: " ",
    EQ: "＝",
    LT: "＜",
    GT: "＞"
};


///////////////// Record Class
/**
 * 识别过程的一行记录
 * @param {number} step
 * @constructor
 */
function Record(step) {
    /**
     * 第几步
     * @type {number}
     */
    this.step = step;
    /**
     * 栈
     * @type {Array.<Symbol>}
     */
    this.stack = [];
    /**
     * 栈内首终结字符与下一个符号的关系
     * @type {string}
     */
    this.relation = Compare.NUL;
    /**
     * 下一个符号
     * @type {Symbol}
     */
    this.next = undefined;
    /**
     * 其余的输入部分
     * @type {Array.<Symbol>}
     */
    this.input = [];
    /**
     * 最左质短语
     * @type {Array.<Symbol>}
     */
    this.phrase = [];
}


/////////////// Symbol Class
/**
 * 字符类
 * @param {String} exp
 * @constructor
 */
function Symbol(exp) {
    /**
     * 符号表示
     * @type {String}
     */
    this.sym_exp = exp;
    this.sym_vt = false;
}

Symbol.prototype.toString = function () {
    return this.sym_exp;
};


///////////////////// Syntax Class
/**
 * 重写规则类
 * @param {Symbol} left
 * @param {Array.<Symbol>} right
 * @constructor
 */
function Syntax(left, right) {
    /**
     * 重写规则的左部
     * @type {Symbol}
     */
    this.syn_left = left;
    /**
     * 重写规则的右部
     * @type {Array.<Symbol>}
     */
    this.syn_right = right;
}

Syntax.prototype.toString = function () {
    return this.syn_left + "::=" + this.syn_right.join("");
};


////////////////// Grammar Class
/**
 * 文法类
 * @param {Syntax|Array.<Syntax>} [syn]
 */
function Grammar(syn) {
    /**
     * 终结字符集
     * @type {Set.<Symbol>}
     */
    this.gra_tc = new Set();
    /**
     * 非终结字符集
     * @type {Set.<Symbol>}
     */
    this.gra_nc = new Set();
    /**
     * 重写规则集合
     * @type {Set.<Syntax>}
     */
    this.gra_sc = new Set();
    /**
     * FirstVt 集合
     * @type {Map.<Symbol, Set.<Symbol>>}
     */
    this.gra_firstVt = new Map();
    /**
     * LastVt 集合
     * @type {Map.<Symbol, Set.<Symbol>>}
     */
    this.gra_lastVt = new Map();
    /**
     * 等于关系
     * @type {Map.<Symbol, Set.<Symbol>>}
     */
    this.gra_equ = new Map();
    /**
     * 算符优先矩阵
     * @type {Map.<Symbol, Map.<Symbol, String>>}
     */
    this.gra_matrix = new Map();
    /**
     * 识别过程表
     * @type {Array.<Record>}
     */
    this.gra_table = [];
    this.gra_succeed = false;
    if (!!syn) {
        this.addSyntax(syn);
    }
}

/**
 * 将某组字符放入终结字符集
 * @param {Array.<Symbol>} syms
 */
Grammar.prototype.add2TC = function (syms) {
    var i, j;
    lvl_0:
        for (i = 0; i < syms.length; ++i) {
            for (j = 0; j < this.gra_nc.size; ++j) {
                if (syms[i].toString() === this.gra_nc.get(j).toString()) {
                    continue lvl_0;
                }
            }
            this.gra_tc.add(syms[i]);
            syms[i].sym_vt = true;
        }
};

/**
 * 将某个字符放入非终结字符集
 * @param {Symbol} sym
 */
Grammar.prototype.add2NC = function (sym) {
    sym.sym_vt = false;
    this.gra_nc.add(sym);
    this.gra_tc.remove(sym);
};

/**
 * 将属性存入类
 * @param {Syntax} syn
 */
Grammar.prototype.add2Attr = function (syn) {
    this.gra_sc.add(syn);
    this.add2NC(syn.syn_left);
    this.add2TC(syn.syn_right);
};

/**
 * 加入文法
 * @param {Syntax|Array.<Syntax>} syn
 */
Grammar.prototype.addSyntax = function (syn) {
    var i;
    if (syn instanceof Syntax) {
        this.add2Attr(syn);
    } else if (syn instanceof Array) {
        for (i = 0; i < syn.length; ++i) {
            this.add2Attr(syn[i]);
        }
    }
};

/**
 * 求解 FirstVt 与 LastVt  相等关系
 */
Grammar.prototype.find = function () {
    var i, j, syn, first_time = true, finish = false,
        first = this.gra_firstVt,
        last = this.gra_lastVt,
        equ = this.gra_equ;
    first.clear();
    last.clear();
    equ.clear();
    // 初始化 firstVt 与 lastVt
    for (i = 0; i < this.gra_nc.size; ++i) {
        first.put(this.gra_nc.get(i), new Set());
        last.put(this.gra_nc.get(i), new Set());
    }
    while (!finish) {
        finish = true;
        for (i = 0; i < this.gra_sc.size; ++i) {
            syn = this.gra_sc.get(i);
            if (first_time) {
                // 寻找等于关系
                var equ_key = undefined;
                for (j = 0; j < syn.syn_right.length; ++j) {
                    if (syn.syn_right[j].sym_vt) {
                        if (!!equ_key) {
                            if (!equ.has(equ)) {
                                equ.put(equ_key, new Set());
                            }
                            equ.get(equ_key).add(syn.syn_right[j]);
                        }
                        equ_key = syn.syn_right[j];
                    }
                }
                // 第一次寻找 firstVt
                for (j = 0; j < syn.syn_right.length; ++j) {
                    if (syn.syn_right[j].sym_vt) {
                        first.get(syn.syn_left).add(syn.syn_right[j]);
                        break;
                    }
                }
                // 第一次寻找 lastVt
                for (j = syn.syn_right.length - 1; j >= 0; --j) {
                    if (syn.syn_right[j].sym_vt) {
                        this.gra_lastVt.get(syn.syn_left).add(syn.syn_right[j]);
                        break;
                    }
                }
                finish = false;
            } else {
                if (!syn.syn_right[0].sym_vt && !first.get(syn.syn_left).contains(first.get(syn.syn_right[0]))) {
                    first.get(syn.syn_left).addSet(first.get(syn.syn_right[0]));
                    finish = false;
                }
                if (!syn.syn_right[syn.syn_right.length - 1].sym_vt
                    && !last.get(syn.syn_left).contains(last.get(syn.syn_right[syn.syn_right.length - 1]))) {
                    last.get(syn.syn_left).addSet(last.get(syn.syn_right[syn.syn_right.length - 1]));
                    finish = false;
                }
            }
        }
        first_time = false;
    }
};

/**
 * 计算并存入算符优先矩阵
 */
Grammar.prototype.generateMatrix = function () {
    var matrix = this.gra_matrix;
    var i, j, k, tmp, tmp2;
    matrix.clear();
    // 初始化 matrix 变量
    for (i = 0; i < this.gra_tc.size; ++i) {
        matrix.put(this.gra_tc.get(i), new Map());
        for (j = 0; j < this.gra_tc.size; ++j) {
            matrix.get(i).put(this.gra_tc.get(j), Compare.NUL);
        }
    }
    // equal
    for (i = 0; i < this.gra_equ.size; ++i) {
        tmp = this.gra_equ.get(i);
        for (j = 0; j < tmp.size; ++j) {
            matrix.get(this.gra_equ.getKey(i)).set(tmp.get(j), Compare.EQ);
        }
    }
    // LT & GT
    for (i = 0; i < this.gra_sc.size; ++i) {
        tmp = this.gra_sc.get(i); // every syntax
        for (j = 0; j < tmp.syn_right.length; ++j) {
            if (tmp.syn_right[j].sym_vt) {
                if (j > 0 && !tmp.syn_right[j - 1].sym_vt) {
                    tmp2 = this.gra_lastVt.get(tmp.syn_right[j - 1]);
                    for (k = 0; k < tmp2.size; ++k) {
                        matrix.get(tmp2.get(k)).set(tmp.syn_right[j], Compare.GT);
                    }
                }
                if (j < tmp.syn_right.length - 1 && !tmp.syn_right[j + 1].sym_vt) {
                    tmp2 = this.gra_firstVt.get(tmp.syn_right[j + 1]);
                    for (k = 0; k < tmp2.size; ++k) {
                        matrix.get(tmp.syn_right[j]).set(tmp2.get(k), Compare.LT);
                    }
                }
            }
        }
    }
};

/**
 * 由 former 和 latter 得出优先关系
 * @param {Symbol} former
 * @param {Symbol} latter
 * @returns {String}
 */
Grammar.prototype.getComparison = function (former, latter) {
    return this.gra_matrix.get(former).get(latter);
};

/**
 * @returns {Array}
 */
Grammar.prototype.getComparisonArray = function () {
    var i, j;
    var ret = [], tmp = [];
    tmp.push(undefined);
    Array.prototype.push.apply(tmp, this.gra_tc.con);
    ret.push(tmp);
    for (i = 0; i < this.gra_matrix.size; ++i) {
        var row = [this.gra_matrix.getKey(i)],
            rMap = this.gra_matrix.get(i);
        for (j = 1; j < tmp.length; ++j) {
            row.push(rMap.get(tmp[j]));
        }
        ret.push(row);
    }
    return ret;
};

/**
 * 由矩形给出的归约步骤
 * @param {number} step
 * @param {Array.<Symbol>} stack
 * @param {Symbol} next
 * @param {Array.<Symbol>} input
 */
Grammar.prototype.unit = function (step, stack, next, input) {
    if (step === 0) this.gra_table.clear();
    var phrase = [], record = new Record(step), relation = Compare.NUL, i, continu = true;
    if (step === 0 || this.gra_table[step - 1].phrase.length === 0) {
        if (!!next) {
            stack.push(next);
        }
        next = input.shift();
        relation = !stack.top() ? Compare.LT : (!next ? Compare.GT : this.getComparison(stack.top(), next));
    } else {
        var flag = true;
        for (i = 0; i < this.gra_sc.size; ++i) {
            if (this.gra_table[step - 1].phrase.equalsForSymbol(this.gra_sc.get(i).syn_right)) {
                stack.replaceTop(this.gra_sc.get(i).syn_left, this.gra_table[step - 1].phrase.length);
                flag = false;
                break;
            }
        }
        if (flag) {
            this.gra_succeed = false;
            return;
        }
        if (continu = (stack.length !== 1 || !!next || input.length !== 0)) {
            for (i = stack.length - 1; i >= 0; --i) {
                if (stack[i].sym_vt) break;
            }
            relation = i === -1 ? Compare.LT : (!next ? Compare.GT : this.getComparison(stack[i], next));
        }
    }
    record.stack = stack.clone();
    record.relation = relation;
    record.next = next;
    record.input = input.clone();
    if (record.relation === Compare.GT) {
        var sentence = stack.clone();
        if (!!next) {
            sentence.concat(next);
        }
        if (input.length !== 0) {
            sentence.concat(input);
        }
        var endLast = undefined, beginLast = undefined,
            endIndex = -1, beginIndex = -1;
        for (i = 0; beginIndex === -1 && endIndex === -1 && i < sentence.length; ++i) {
            if (sentence[i].sym_vt) {
                if (!!endLast && this.getComparison(endLast, sentence[i]) == Compare.GT) {
                    endIndex = i - 1;
                    break;
                } else {
                    endLast = sentence[i];
                }
            }
        }
        if (endIndex === -1) endIndex = sentence.length - 1;
        for (i = endIndex; i >= 0; --i) {
            if (sentence[i].sym_vt) {
                if (!!beginLast && this.getComparison(sentence[i], beginLast) == Compare.LT) {
                    beginIndex = i + 1;
                    break;
                } else {
                    beginLast = sentence[i];
                }
            }
        }
        if (beginIndex === -1) beginIndex = 0;
        for (i = beginIndex; i <= endIndex; ++i) {
            phrase.push(sentence[i]);
        }
    }
    record.phrase = phrase;
    this.gra_table.push(record);
    if (continu) {
        this.gra_succeed = true;
        this.unit(step + 1, stack, next, input);
    }
};

Grammar.prototype.execute = function () {
    var right, i, j, last;
    for (i = 0; i < this.gra_sc.size; ++i) {
        right = this.gra_sc.get(i).syn_right;
        last = undefined;
        for (j = 0; j < right.length; ++j) {
            if (!!last && !last.sym_vt && !right[j].sym_vt) {
                this.reset();
                return false;
            }
            last = right[j];
        }
    }
    this.find();
    this.generateMatrix();
    return true;
};

Grammar.prototype.reset = function () {
    var a = function (b) {
        if (!b) b.clear();
    };
    a(this.gra_nc);
    a(this.gra_tc);
    a(this.gra_sc);
    a(this.gra_firstVt);
    a(this.gra_lastVt);
    a(this.gra_equ);
    a(this.gra_matrix);
    a(this.gra_table);
};
